Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/misc/volume10/b+tree_mjr/part05

Text File | 1990-01-19 | 45.2 KB | 1,802 lines

Newsgroups: comp.sources.misc
subject: v10i031: B+tree library, part05 of 5
from: [e-mail] (Marcus J. Ranum)
Sender: [e-mail] (Brandon S. Allbery - comp.sources.misc)

Posting-number: Volume 10, Issue 31
Submitted-by: [e-mail] (Marcus J. Ranum)
Archive-name: b+tree_mjr/part05

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 5 (of 5)."
# Contents:  b+tree/doc/btree.3 b+tree/utils/btest.c
# Wrapped by mjr@atreus on Fri Jan 19 10:34:59 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'b+tree/doc/btree.3' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/doc/btree.3'\"
else
echo shar: Extracting \"'b+tree/doc/btree.3'\" \(24047 characters\)
sed "s/^X//" >'b+tree/doc/btree.3' <<'END_OF_FILE'
X.\"
X.\"         (C) Copyright, 1988, 1989 Marcus J. Ranum
X.\"                    All rights reserved
X.\"
X.\"
X.\"          This software, its documentation,  and  supporting
X.\"          files  are  copyrighted  material  and may only be
X.\"          distributed in accordance with the terms listed in
X.\"          the COPYRIGHT document.
X.\"
X.\" $Header: /atreus/mjr/hacks/btree/doc/RCS/btree.3,v 1.4 89/10/23 15:37:43 mjr Rel $
X.\"
X.TH B\+TREE 3 "30 September 1989"
X.SH NAME
Xb+tree \- variable length b+tree index management package
X.SH SYNOPSIS
X.B #include <sys/types.h>
X.br
X.B #include <btree.h>
X.sp
X.LP
X.B "BT_INDEX bt_open(path,flags,mode)"
X.br
X.B "char *path;"
X.br
X.B "int flags;"
X.br
X.B "int mode;"
X.LP
X.B #include <varargs.h>
X.br
X.B "BT_INDEX bt_optopen(va_alist)"
X.LP
X.B "int bt_delete(btree,key,len)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.LP
X.B "int bt_find(btree,key,len,rrn)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.br
X.B "off_t *rrn;"
X.LP
X.B "int bt_goto(btree,d)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "int d; /* BT_EOF or BT_BOF */"
X.LP
X.B "int bt_insert(btree,key,len,rrn,dupflg)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.br
X.B "off_t rrn;"
X.br
X.B "int dupflg;"
X.LP
X.B "int bt_traverse(btree,d,kbuf,maxlen,retlen,retrrn)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "int d; /* BT_EOF or BT_BOF */"
X.br
X.B "bt_chrp kbuf;"
X.br
X.B "int maxlen;"
X.br
X.B "int *retlen;"
X.br
X.B "off_t *retrrn;"
X.LP
X.B "void bt_perror(btree,s)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "char *s;"
X.LP
X.B "int bt_rlabel(btree,buf,siz)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp buf;"
X.br
X.B "int siz;"
X.LP
X.B "int bt_wlabel(btree,buf,siz)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp buf;"
X.br
X.B "int siz;"
X.LP
X.B "int bt_sync(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "int bt_close(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "int bt_load(btree,key,len,rrn,flag)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.br
X.B "off_t rrn;"
X.br
X.B "int flag; /* either BT_BOF, BT_OK, or BT_EOF */"
X.LP
X.B "int bt_zap(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "The following are macros:"
X.LP
X.B "(int) bt_fileno(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(int) bt_pagesiz(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(int) bt_dtype(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(*int)() bt_cmpfn(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(int) bt_errno(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(void) bt_clearerr(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(int) BT_MAXK(btree)"
X.br
X.B "BT_INDEX *btree;"
X.LP
X.B "(int) BT_LABSIZ(btree)"
X.br
X.B "BT_INDEX *btree;"
X.SH DESCRIPTION
X.LP
XThe b+tree library implements a variable-length key variable page size b+tree.
XA variety of options are supported, including user-settable cache modes,
Xcache sizes, user defined data types, and several system defined data types.
XSupport for variable length string keys with automatic prefixing is built
Xin. The library does \fINOT\fR support any means of data storage for anything
Xmore than keys - for that the user must have access to a record management
Xlibrary (such as
X.B "store(3)"
Xor
X.B "btdbm(3)"
X\).
X.LP
XThe b+tree library stores all keys as variable length blocks of
Xunsigned chars, and associates a \fIRemote Record Number (RRN)\fP
Xwith each key. This is defined as the typedef
X.B off_t
Xand is typically used to store a disk address of a record someplace
Xelse in secondary storage. There is no provision for storing more
Xassociated data than the \fIRRN\fP in the index.
XThe typedef
X.B bt_chrp
Xis provided to increase portability and should be used in preference to
Xa char pointer, though they may really be the same type.
X.SH "INITIALIZING A B+TREE"
X.LP
XWhen a b+tree is opened, an attempt is made to read a block of information
Xat the beginning of the file which contains parameters such as page size, etc.
XIf no bytes are read, indicating the file is empty, this is
Xtaken as an indication that the file should be initialized, and a new b+tree
Xis created. To prevent confusion, a variety of checks are made, including
Xverifying that a magic number is correct, and that any parameters provided
Xmake sense. If the open succeeds, a pointer to a dynamically allocated
Xb+tree index is returned. In the event of an error, a NULL pointer is
Xreturned.
X.LP
XIf an existing b+tree is re-opened, the information in the header block
Xmay override any options from the user, if appropriate. Thus, if a b+tree
Xhas already been created with one page size, attempts to use a different
Xpage size are politely ignored.
X.SH "OPENING A B+TREE"
X.LP
XThere are two functions provided for opening a b+tree. The first,
X.B "bt_open()"
Xis intended to look like the
X.B "open(2)"
Xsystem call, and assumes that the caller wishes to open a b+tree with
Xall the default options. These defaults are built into the library,
Xand set the page size to some reasonable value in view of the system buffer
Xsize, cache size to some reasonable value, cache modes to something
Xconservative, and the b+tree data type to string.
X.LP
XThe second function for opening a b+tree,
X.B "bt_optopen()"
Xallows a user to set a larger variety of options. The interface to the
Xfunction is through a variable length argument list, terminated by a
Xzero. Each of the arguments is interpreted in sequence as a request
Xfor a specific parameter in the b+tree to be set.
XEach request may be followed by one
Xor more arguments, depending on the specific request. Omission of an
Xargument, or the terminating zero will result in disaster. Not all of
Xthe request are required, and if the request is omitted, the default
Xwill be taken. Those marked as mandatory must be provided.
X.LP
X.B "Options to bt_optopen()"
X.LP
X.I BT_PATH:
XThis option must be followed by a null-terminated string specifying the
Xpath name of the file to open. \fIThis value must be provided\fR.
X.LP
X.I BT_PSIZE:
XThis option must be followed by an integer value indicating the desired
Xpage size to use. The default is to use a value based on the system
Xbuffer size.
X.LP
X.I BT_CACHE:
XThis option must be followed by an integer value specifying the number
Xof cache buffers to use in addition to
Xthe minimum number of cache buffers required for scratch pages. The
Xdefault is to use a reasonable sized cache, which should be adequate.
X.LP
X.I BT_CFLAG:
XThis option must be followed by a flag value which specifies the manner
Xin which cache buffers are to be handled. The permitted values are
Xdefined as
X.I BT_NOCACHE
X.I BT_ROCACHE
Xor
X.I BT_RWCACHE
Xstanding for (respectively) no cache, read-only cache, and read-write
Xcache. The effects of these values is as follows: When no cache is
Xindicated, pages are read from disk every time a read request is issued,
Xand are written to disk with every write request. The minimal existing
Xcache buffers are still required for splitting and insertion, but data
Xis never taken from them. When read-only cache is in effect, reads may
Xbe returned directly out of cache, but all page write requests are still
Xflushed immediately to disk. This means that programs which exit suddenly
Xfor some reason or another need be less concerned about whether or not
Xthe b+tree index has been flushed. The read-write cache option allows
Xpages to be written directly into cache, where they are only flushed to
Xdisk when expired, or the tree is closed. This mode should save some
Xtime when building an index in batch mode. At any time, the
X.B "bt_sync()"
Xfunction can be called to flush any modified pages to disk. Closing
Xa b+tree also flushes the cache.
X.LP
X.I BT_OMODE:
XThis option must be followed by an integer value which is used as flags
Xto the
X.B "open(2)"
Xsystem call.
X.LP
X.I BT_OPERM:
XThis option must be followed by an integer value which is passed to the
X.B "open(2)"
Xsystem call as the permissions information.
X.LP
X.I BT_MAGIC:
XThis option must be followed by a long value which is used as the
Xmagic number for the b+tree. This replaces the default value. One
Xside-effect of setting this value is that the correct value \fImust\fR
Xbe provided again if the tree is re-opened.
X.LP
X.I BT_DTYPE:
XThis option must be followed by a flag value indicating the type of
Xdata that is being stored in the index. The permitted values are
Xdefined as
X.I BT_STRING
X.I BT_INT
X.I BT_LONG
X.I BT_FLOAT
Xand
X.I BT_USRDEF
Xmeaning either string, integer, long, float, or user-defined. The string
Xdata type is the default, and there are functions built into the tree
Xthat improve string performance. Depending on the system architecture,
Xthe compiler, etc, you may have trouble with floats, ints, and longs,
Xas well as user-defined data, due to alignment problems. This can be
Xgotten around only in system-specific ways, so no solution is offered
Xhere.
X.LP
XIf the
X.I BT_USRDEF
Xflag is passed, another value must be passed as well, being a pointer
Xto a function returning an integer - the comparison function. This
Xfunction is expected to be called as:
X.br
X.B "(*cmpf)(key1,length1,key2,length1);"
X.br
Xwhere \fIkey1\fR is the first key, and \fIlength1\fR is its length,
Xand \fIkey2\fR is the second key, with \fIlength2\fR as its length.
XThe function is expected to return zero if the two keys are equal
Xin sort order, a value less than zero if the first key is less than
Xthe second key, and a value greater than zero if the first key is
Xgreater than the second. when using the user-defined data structures,
Xsince the keys may be variable-length, the user is responsible for
Xstructure alignment and other nasties. As long as the keys are a multiple
Xof the system word size, there should be no alignment problems.
X.LP
X.I BT_LABEL:
XThis option must be followed by a character pointer and an integer
Xvalue. The character pointer is used as a label, and is stored in
Xsome spare space at the end of the b+tree file header. The integer
Xvalue must contain the length of the label being provided. If there
Xis insufficient room in the b+tree file header, an error will result.
XThe label can also be read and set using the
X.B "bt_rlabel()"
Xand
X.B "bt_wlabel()"
Xfunctions.
X.SH "BT_OPTOPEN EXAMPLES"
X.nf
X.na
X.ft C
X    BT_INDEX    *p;
X
X    p = bt_optopen(    BT_PATH, "test.dat",
X            BT_MODE, 0600,
X            BT_OMODE, O_CREAT|O_TRUNC,
X            BT_CFLAG, BT_RWCACHE,
X            0);
X.ft R
X.fi
X.ad
X.LP
XThe above would open \fItest.dat\fR with mode 0600, and would create
Xor truncate an existing file. Since the file will be truncated, a new
Xb+tree index will be initialized. The data type of the index will be
Xthe default, as will the cache size. The cache, however, has been
Xflagged to not immediately flush pages to disk on write.
X.br
X.sp
X.nf
X.na
X.ft C
X    BT_INDEX    *p;
X    extern        int    mycompare();
X
X    p = bt_optopen(    BT_PATH, "test2.dat",
X            BT_DTYPE, BT_USRDEF, mycompare,
X            BT_PSIZE, (BUFSIZ * 2),
X            BT_LABEL, "foo", 3,
X            0);
X.ft R
X.fi
X.ad
X.LP
XThe above would open \fItest2.dat\fR with page size of double the system
Xbuffer size. The data type stored is indicated to be user-defined, and
Xa comparison function
X.B "mycompare()"
Xis provided to compare keys. The b+tree index is labeled \fIfoo\fR for
Xmysterious reasons.
X.SH "OTHER B+TREE FUNCTIONS"
X.LP
X.B "int bt_delete(btree,key,len)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.br
XThis function will search for the key and delete it from the index. If the
Xkey is not present in the index, the value
X.B BT_NF
Xis returned.
X.LP
X.B "int bt_find(btree,key,len,rrn)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.br
X.B "off_t *rrn;"
X.br
XThis function will search for the key and store the data pointer in
X.B rrn,
Xreturning
X.B BT_NF
Xif the key is not present in the index. The current location in the
Xindex is stored to "point" to the located key, or to the key
Xwhere it should have been if it was not present.
X.LP
X.B "int bt_goto(btree,d)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "int d; /* BT_EOF or BT_BOF */"
X.br
XThis function will move the current b+tree location to either the
Xhighest key in the tree or the lowest, depending on the value in
X.B d.
XIf the value is
X.B BT_EOF
Xthe locator will be moved to the highest key in the tree, if it is
X.B BT_BOF
Xthe locator moves to the lowest key. The current location in the
Xindex is stored if the call is successful.
X.LP
X.B "int bt_insert(btree,key,len,rrn,dupflg)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp key;"
X.br
X.B "int len;"
X.br
X.B "off_t rrn;"
X.br
X.B "int dupflg;"
X.br
XThis function inserts the key in an index, with the data pointer
Xvalue in
X.B rrn.
XDuplicate keys are not supported, and
X.B BT_ERR
Xwill be returned if an attempt is made to insert a duplicate value,
Xunless
X.B dupflg
Xis non-zero, in which case the value in
X.B rrn
Xis used to replace the value currently stored in the index as a
Xdata pointer. This operation is more efficient than deleting a key
Xand re-inserting it, and should be used where changing the
Xdata pointer is desired. When a new key is inserted in the index,
Xthe current location in the index is invalidated. Thus, inserting a
Xkey and calling
X.B bt_traverse
Xwill cause a seek to the beginning or the end of the index.
X.LP
X.B "int bt_traverse(btree,d,kbuf,maxlen,retlen,retrrn)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "int d; /* BT_EOF or BT_BOF */"
X.br
X.B "bt_chrp kbuf;"
X.br
X.B "int maxlen;"
X.br
X.B "int *retlen;"
X.br
X.B "off_t *retrrn;"
X.br
XThis function will move forward or backwards across the keys in the
Xtree, depending on the value in
X.B d.
XIf the value in
X.B d
Xis
X.B BT_EOF
Xthe traverse will move towards the high end of the index, if it is
X.B BT_BOF
Xthe traverse will move towards the low end. If the traverse is
Xsuccessful, the next (or previous) key is placed in
X.B kbuf,
Xthe data pointer in
X.B retrrn,
Xand the length of the key is stored in
X.B retlen.
X.B maxlen
Xis checked to ensure that there is sufficient room in the user-provided
Xbuffer for the key, to prevent overruns. If an overrun would occur, the
Xfunction returns
X.B BT_ERR
Xand
X.B bt_errno
Xfor the index is set to
X.B BT_BTOOSMALL.
XIf the end of the index is encountered, and the traverse can proceed no
Xfurther, the value
X.B BT_EOF
Xis returned by the function, or
X.B BT_BOF
Xis returned if the beginning of the index is reached. If the current
Xlocation in the index is undefined at the time of the call to
X.B bt_traverse
Xa
X.B bt_goto
Xis performed to the \fIopposite\fR end of the index from the direction
Xin which the traverse is being performed. In this way, a tree can be
Xopened and dumped by simply performing successive calls to
X.B bt_traverse.
X.LP
X.B "void bt_perror(btree,s)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "char *s;"
X.br
XThis function prints out any error messages currently associated with
Xthe index, in the manner of the
X.B "perror(3)"
Xfunction. If there is no current error detected in the index, and a
Xsystem error is present in
X.B errno,
X.B perror
Xis called with the string
X.B s.
X.LP
X.B "int bt_rlabel(btree,buf,siz)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp buf;"
X.br
X.B "int siz;"
X.br
XThis function reads the label from the index and places it in
X.B buf,
Xchecking the value of
X.B siz
Xto ensure there is enough room. Note that the software keeps no count of
Xhow many bytes of data are in the label.
X.LP
X.B "int bt_wlabel(btree,buf,siz)"
X.br
X.B "BT_INDEX *btree;"
X.br
X.B "bt_chrp buf;"
X.br
X.B "int siz;"
X.br
XThis function writes the contents of
X.B buf,
Xto the index label, consisting of
X.B siz
Xbytes.
X.LP
X.B "int bt_sync(btree)"
X.br
X.B "BT_INDEX *btree;"
X.br
XThis function causes any dirty cache buffers in the index buffer cache to
Xbe flushed to disk.
X.LP
X.B "int bt_close(btree)"
X.br
XThis function closes a b+tree index and frees all dynamically allocated
Xmemory.
X.LP
X.B "int bt_load(btree,key,len,rrn,flag)"
X.br
XThis function performs an optimal in-order load of a set of keys. The keys
Xmust be presented in \fBREVERSE\fP sort order. The advantages this function
Xconfers are several, and it should be used any time an index is being
Xbulk-loaded, or is being rebuilt. When an index is built with
X.B bt_load
Xthe pages are filled in descending order, rather than through random
Xaccess search as in
X.B bt_insert.
XAdditionally, each page is filled to capacity, which means that less space
Xis taken up for the index, and less time is required to search the index.
XFor large indices, the benefit of occasionally optimizing the index by
Xrebuilding it with
X.B bt_load
Xcannot be sufficiently emphasized. Storage savings up up to 50% can be
Xrealized, and search efficiency can be improved considerably.
X.LP
XTo use
X.B bt_load,
Xthe function must first be called on an empty index, or one that is
Xdisposable, with the
X.B key,
X.B len,
Xand
X.B rrn
Xvalues equal to zero. The
X.B flag
Xargument must be
X.B BT_BOF
Xindicating that the file is to be initialized.
XThis causes the tree to be re-initialized through a call to
X.B bt_zap.
XOnce the first call the
X.B bt_load
Xhas been made, any number of subsequent calls can be made, with
X.B key,
X.B len,
Xand
X.B rrn
Xvalues to insert in the index. The
X.B flag
Xargument should be set to
X.B BT_OK
Xto indicate that the keys are valid keys.
XAfter all the keys have been inserted, a final call to
X.B bt_load
Xmust be made, with the
X.B key,
X.B len,
Xand
X.B rrn
Xequal to zero again, and the
X.B flag
Xargument equal to
X.B BT_EOF
Xindicating that the end of the load has been reached. At that time,
Xfurther clean-up is performed, and the new b+tree index can be used
Xnormally.
X.LP
XFor purposes of performance in running
X.B bt_load
Xhaving a reasonable sized cache (about 3 spare pages) and the cache
Xflags set to
X.B BT_RWCACHE
Xwill reduce load times. Increasing the cache by more than a
Xmoderate amount will not drastically improve load times, since the
Xindex is not searched during inserts.
X.LP
XDuring any of the calls to
X.B bt_load
Xif an error condition is encountered, the usual
X.B BT_ERR
Xwill be returned. If the error is anything more serious than an
Xoversized key, or zero-length key, the index will be unusable.
X.LP
X.B "int bt_zap(btree)"
X.br
XThis function resets the b+tree index to an empty state, while retaining
Xany set values for page size, etc. Note that this function will only free
Xdisk space that has been allocated on systems that have the
X.B "ftruncate(2)"
Xsystem call. In order to free disk space on systems that do not
Xhave
X.B ftruncate
Xthe index file must be unlinked and re-created.
X.SH "MACROS"
X.LP
XSince these values are all macros, they should be used only with
Xcaution, to avoid side-effects. Mostly these should not be used by
Xuser-level code, but providing a common interface seemed better
Xthan the alternative.
X.LP
X.B "bt_fileno(btree)"
Xpoints to the file descriptor (integer value) of the index. Users should not
Xfiddle with this unless they know what they're about.
X.LP
X.B "bt_pagesiz(btree)"
Xpoints to the size (integer value) of the b+tree index pages.
X.LP
X.B "bt_dtype(btree)"
Xpoints to the data type if the index. It will be one of the values
Xdiscussed in opening a b+tree.
X.LP
X.B "bt_cmpfn(btree)"
Xpoints to the comparison function used by user-defined data type b+trees.
XIt is possible to reset this on the fly, though the results are not under
Xwarranty.
X.LP
X.B "bt_errno(btree)"
Xpoints to the integer error number value. Definitions of the error codes
Xare in
X.B "btree.h".
X.LP
X.B "bt_clearerr(btree)"
Xresets the index error value to indicate there is no error. This is
Xperformed automatically after every successful function call.
X.LP
X.B "BT_MAXK(btree)"
Xyields an integer value that gives the largest possible size that a
Xkey can be, given the page size of the b+tree. This size is actually
Xsmaller than the largest size of a key that can really be fit in a
Xpage, but is calculated to reliably permit even splitting and promotion.
X.LP
X.B "BT_LABSIZ(btree)"
Xyields an integer value that gives the largest possible amount of
Xspace that can be used for an index label.
X.SH "SEE ALSO"
X.SH "INTERNAL FUNCTIONS"
X.LP
XThe following functions are internal functions used by the b+tree library.
XCare should be taken to avoid declaring functions with names that clash:
X.B bt_delpg,
X.B bt_dump,
X.B bt_freepage,
X.B bt_genprx,
X.B bt_inspg,
X.B bt_keyof,
X.B bt_newpage,
X.B bt_requeue,
X.B bt_rpage,
X.B bt_seekdown,
X.B bt_splpg,
X.B bt_srchpg,
X.B bt_wpage,
X.B bt_wsuper
X.LP
XIn general, all the b+tree functions
Xand macros are prefixed with
X.B bt_...
Xand constants with
X.B BT_...
X.SH DIAGNOSTICS
X.LP
XThe value
X.B BT_OK
Xis returned whenever a function is successful.
X.LP
XThe value
X.SM
X.B BT_ERR
Xis returned to indicate some form of failure in any operation performed on
Xa valid
X.B BT_INDEX.
XAll valid b+tree indices contain their own error number that is set to
Xindicate the cause of a failure, and can be accessed with the macro
X.B "bt_errno(btindex)"
X(where
X.B btindex
Xis a valid b+tree index). A function
X.B "bt_perror(btindex,string)"
X(where
X.B string
Xis a character pointer and
X.B btindex
Xis a valid b+tree index) is provided, which prints an appropriate error
Xmessage on the standard error. If the error is not b+tree-related, any
Xexisting system messages apropos existing conditions are printed by
Xcalling
X.B "perror()"
XAdditionally, access to the error strings is available through the
Xexternal array
X.B "bt_errs[]".
XConstant value codes for each error are defined in
X.B btree.h
Xfor symbolic reference.
X.LP
XErrors are cleared after every successful call to a function. They can
Xalso be cleared using the
X.B "bt_clearerr()"
Xmacro.
X.LP
XThe value
X.SM
X.B NULL
Xis returned to indicate that a
X.SM
X.B BT_INDEX
Xpointer has not been initialized properly. Since no valid
X.B BT_INDEX
Xis returned,
X.B "bt_perror()"
Xcannot be used to determine the nature of an error.
X.LP
XThe values
X.B BT_EOF
Xand
X.B BT_BOF
Xare returned if a call to
X.B "bt_traverse()"
Xreaches the end or beginning of the index.
X.LP
XThe value
X.B BT_NF
Xis returned if a call to
X.B "bt_find()"
Xfails to find the requested key, but encounters no error.
X.SH BUGS
X.LP
XThere may be problems with pointer alignment on some architectures,
Xespecially if arbitrary structure alignment is not supported.
X.LP
XDue to the alignment problem, users defining their own data types must
Xbe careful to keep them of such a size that they align well, depending
Xon architecture. Fixed-size user-defined structures will probably
Xbenefit by being padded out to some alignment boundary. Variable-size
Xuser-defined structures should perform thier own padding, even if
Xit requires wasting some space.
X.SH LIMITATIONS
X.LP
XEvery effort has been made to eliminate gratuitous limitations. There
Xis no built-in limit to the depth allowed a tree, as an internal stack
Xis maintained dynamically. There is no built-in limit to page sizes,
Xnumbers of keys, etc, except those inherent in the
Xarchitecture. There is no fixed size to the internal cache, though
Xthere is a fixed minimum that will always be allocated for use as
Xscratch buffers for page splitting, etc. When not being used as such,
Xthey are used to cache disk pages. Assume that at least 4 buffers
Xwill always be allocated.
X.SH ALGORITHMS
X.LP
XThe algorithms used are basically the standard b+tree algorithm as
Xdescribed in countless texts. Some shortcuts are made. Since the
Xkeys can be variable length, the order of the tree is, perforce,
Xvariable. Splitting tries to fill roughly 1/2 of each page during
Xa split, but with a deliberate bias towards the lower page in the
Xsplit, since that is the one which may give up a key for promotion
Xif the page is an internal one. Unlike some b+trees that have two
Xdifferent page structures for internal and leaf pages, this library
Xuses the same structure for both, since no data is stored in the
Xleaf. There is minor wastage as a result, but the size of the
Xobject code is kept down.
X.LP
XDeletes are not implemented in accordance
Xwith the b+tree algorithm, in that pages are not combined as they
Xempty, nor are keys redistributed.  A result is that search performance
Xdoes not improve much as a tree empties, though it does not get
Xworse either. Another side-effect is that while pages may empty out,
Xif the index is re-filled, the inserts will be more efficient,
Xsince the likelihood of having to split a page drops. These assumptions
Xhold true as long as the data is roughly randomly distributed across
Xits range.
X.SH AUTHOR
X.LP
XMarcus J. Ranum
END_OF_FILE
if test 24047 -ne `wc -c <'b+tree/doc/btree.3'`; then
    echo shar: \"'b+tree/doc/btree.3'\" unpacked with wrong size!
fi
chmod +x 'b+tree/doc/btree.3'
# end of 'b+tree/doc/btree.3'
fi
if test -f 'b+tree/utils/btest.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/utils/btest.c'\"
else
echo shar: Extracting \"'b+tree/utils/btest.c'\" \(18333 characters\)
sed "s/^X//" >'b+tree/utils/btest.c' <<'END_OF_FILE'
X#include    <stdio.h>
X#include    <ctype.h>
X#include    <sys/types.h>
X#include    <sys/file.h>
X#include    "btree.h"
X
X/*
X         (C) Copyright, 1988, 1989 Marcus J. Ranum
X                    All rights reserved
X
X
X          This software, its documentation,  and  supporting
X          files  are  copyrighted  material  and may only be
X          distributed in accordance with the terms listed in
X          the COPYRIGHT document.
X*/
X
X
X/*
X    this program does pretty much one of everything to do with the
X    b+tree library. it does the usual deletes, scans, dumps, etc,
X    and shows a few of the tricks that can be done with user defined
X    data types, builtin data types, and so forth. no attempt is
X    made to make the code gorgeous, rather simple and readable.
X
X    in a real application, some of the things done here should NOT
X    be done. the dump structure code and page dump code relies on
X    internal stuff. for real user-level applications, anything
X    that includes btinternal.h is making a BIG mistake and is
X    poking its nose where it should not. users should not make
X    calls to bt_rpage() unless they are doing something that has
X    been carefully thought out. besides, that internal code
X    could change without warning. every attempt will be made to
X    keep the interface to the user-level functions the same,
X    despite any internal mods.
X
X    Enjoy!
X        --mjr();
X*/
X
X/* only included because this uses some internal routines */
X#include    "btconf.h"
X#include    "btintern.h"
X
X#ifndef    lint
Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/utils/RCS/btest.c,v 1.1 89/10/24 10:09:28 mjr Rel $";
X#endif
X
X/*    do not judge the library code by this humble test harness    */
X/*    the globals are simply a convenience, here where it matters not    */
XBT_INDEX    *globf = NULL;    /* global index handle */
X
X#define    MAXARG    40
Xchar    *globargv[MAXARG];        /* args for commands */
Xint    globargc;
Xchar    globname[500];
X
X/* for tweaking, using big pages is boring */
X#define    TESTPSIZ    61
X
Xextern    char    *strcpy();
Xextern    char    *malloc();
Xextern    char    *rindex();
Xextern    long    atol();
Xextern    float    atof();
X
Xvoid do_open(), do_close(), do_quit(), do_wlabel(), printk();
Xvoid do_insert(), do_help(), do_zap(), do_stats(), do_revload();
Xvoid do_find(), do_head(), do_tail(), do_dump(), do_load();
Xvoid do_next(), do_prev(), do_rlabel(), do_delete();
X
Xvoid    enargv();    /* function to parse user args into strings */
Xvoid    doit();        /* dispatch function */
Xcaddr_t    encode();    /* user argument encoder funct. */
X
X/* this is the comparison function needed for the sample user-defined data */
Xint mycompare();
X
X/* and this is the sample data structure */
Xstruct    point    {
X    int    xcoord;
X    int    ycoord;
X};
X
X#ifdef    YES_BT_DEBUG
Xvoid do_pagedump(), do_struct();
X#endif
X
Xstruct    cmd {
X    char    *name;
X    char    *usage;
X    void    (*func)();
X    int    narg;        /* # of args req'd */
X    int    op;        /* needs an open index to call */
X};
X
Xstatic    char    *prompt = "btest->";
X
X/* command dispatch table */
Xstruct    cmd    cmds[] = {
X"close",    "close",            do_close,    1,    1,
X"delete",    "delete key [key2...]",        do_delete,    2,    1,
X"dump",        "dump [-r]",            do_dump,    1,    1,
X"exit",        "exit",                do_quit,    1,    0,
X"find",        "find key",            do_find,    2,    1,
X"head",        "head",                do_head,    1,    1,
X"help",        "help",                do_help,    1,    0,
X"insert",    "insert key [rrn]",        do_insert,    2,    1,
X"label",    "label string",            do_wlabel,    2,    1,
X"load",        "load file (unsorted input)",    do_load,    2,    1,
X"next",        "next [count]",            do_next,    1,    1,
X"open",        "open database [type] [size]",    do_open,    2,    0,
X#ifdef    YES_BT_DEBUG
X"page",        "page page# [page#...]",    do_pagedump,    2,    1,
X#endif
X"plabel",    "plabel (show label)",        do_rlabel,    1,    1,
X"prev",        "prev [count]",            do_prev,    1,    1,
X"quit",        "quit",                do_quit,    1,    0,
X"revload",    "revload file (rev sorted)",    do_revload,    2,    1,
X"stats",    "stats (print internal data)",    do_stats,    1,    1,
X"tail",        "tail",                do_tail,    1,    1,
X#ifdef    YES_BT_DEBUG
X"x",        "x (dump struct)",        do_struct,    1,    1,
X#endif
X"zap",        "zap (toast current index)",    do_zap,        1,    1,
X"?",        "?",                do_help,    1,    0,
X0,        0,                0,        0,    0
X};
X
X
Xmain(ac,av)
Xint    ac;
Xchar    **av;
X{
X    int    x;
X    char    buf[BUFSIZ];
X
X    /* enargv() makes a string look like an arg. vector. */
X    /* doit dispatches the stuff, calls functions, etc */
X    /* functions must have at least the given # of args */
X    /* last flag in a command if not zero means an index */
X    /* must be open in order to call that function */
X
X    if(ac > 1) {
X        char    **gap = globargv;
X
X        globargc = ac - 1;
X        while(*++av)
X            *gap++ = *av;
X        doit();
X    } else {
X        (void)printf(prompt);
X        while(gets(buf)) {
X            enargv(buf);
X            if(globargv[0] != NULL)
X                doit();
X
X            for(x = 0; x < globargc; x++)
X                (void)free(globargv[x]);
X
X            (void)printf(prompt);
X        }
X        (void)printf("EOF.\n");
X    }
X    do_quit();
X}
X
X
Xvoid
Xdoit()
X{
X    struct    cmd    *c = cmds;
X
X    /* main dispatcher */
X    while(c->name != 0) {
X        if(strncmp(c->name,globargv[0],strlen(globargv[0])) == 0) {
X            if(globargc < c->narg) {
X                (void)printf("usage:\"%s\"\n",c->usage);
X                return;
X            } else {
X                if(c->op != 0 && globf == NULL) {
X                    (void)printf("no index open.\n");
X                    return;
X                }
X                (*c->func)();
X                return;
X            }
X        }
X        c++;
X    }
X    (void)printf("unknown command: \"%s\"\n",globargv[0]);
X    return;
X}
X
X
Xchar *
Xwordparse(line,word,delim)
Xchar    *line,    *word;
Xint    delim;
X{
X    int    quot =0;
X
X    /* parse a word, or quoted string into a buffer. */
X    while (*line && (isspace(*line) || *line == delim))
X        line++;
X
X    if(*line == '\n')
X        line++;
X
X    if (!*line) {
X        *word = '\0';
X        return(0);
X    }
X
X    while (*line)
X    {
X        if(!quot && (*line == '\"' || *line == '\''))
X            quot = *line++;
X
X        if((isspace(*line) || *line == delim) && !quot) {
X            break;
X        } else {
X            if(quot && *line == quot) {
X                quot = 0;
X                line++;
X            } else {
X                *word++ = *line++;
X            }
X        }
X    }
X    *word = '\0';
X    return(line);
X}
X
X
Xvoid
Xenargv(buf)
Xchar    *buf;
X{
X    char    *bufptr;
X    char    pbuf[BUFSIZ];
X
X    globargc =0;
X    bufptr = buf;
X
X    /* this is kinda gross, but the easiest way to handle */
X    /* quoted strings, since I already had wordparse() written */
X    while(bufptr = wordparse(bufptr,pbuf,0)) {
X        globargv[globargc] = malloc((unsigned)(strlen(pbuf) + 1));
X        (void)strcpy(globargv[globargc++],pbuf);
X    }
X    globargv[globargc] = NULL;
X}
X
X
Xvoid
Xdo_open()
X{
X    int    ps = TESTPSIZ;
X    int    typ = BT_DFLTDTYPE;
X
X    if(globf != NULL) {
X        (void)printf("try closing %s first, ok ?\n",globname);
X        return;
X    }
X
X#ifdef    BTOPEN
X    if(globargc > 2) {
X        (void)printf("cannot specify data type when using bt_open()\n");
X        return;
X    }
X#else
X    if(globargc > 2) {
X        if(!strcmp(globargv[2],"int")) {
X            typ = BT_INT;
X        } else if(!strcmp(globargv[2],"float")) {
X            typ = BT_FLOAT;
X        } else if(!strcmp(globargv[2],"long")) {
X            typ = BT_LONG;
X        } else if(!strcmp(globargv[2],"string")) {
X            typ = BT_STRING;
X        } else if(!strcmp(globargv[2],"userdef")) {
X            typ = BT_USRDEF;
X        } else {
X            (void)printf("unknown data type \"%s\" - not opened\n",globargv[2]);
X            (void)printf("use: float, string, long, int, or userdef\n");
X            return;
X        }
X    }
X#endif
X
X    if(globargc > 3) {
X        if((ps = atoi(globargv[3])) == 0) {
X            (void)printf("invalid page size 0\n");
X            return;
X        }
X    }
X
X#ifdef    BTOPEN
X    globf = bt_open(globargv[1],O_CREAT,0600);
X#else
X    if(typ != BT_USRDEF) {
X        /* if user-defined we need to pass compare */
X        /* func, too - hence this special case code */
X        globf = bt_optopen(BT_PATH,    globargv[1],
X                BT_OMODE,    O_CREAT,
X                BT_DTYPE,    typ,
X                BT_PSIZE,    ps,
X        0);
X    } else {
X        globf = bt_optopen(BT_PATH,    globargv[1],
X                BT_OMODE,    O_CREAT,
X                /* note - pass the comparison function */
X                BT_DTYPE,    typ,    mycompare,
X                BT_PSIZE,    ps,
X        0);
X    }
X#endif
X
X    if(globf == NULL) {
X        (void)printf("error opening database ");
X        perror(globargv[1]);
X        (void)printf("\n");
X    } else {
X        (void)printf("opened %s, type %d, with page size %d\n",globargv[1],bt_dtype(globf),bt_pagesiz(globf));
X        (void)strcpy(globname,globargv[1]);
X    }
X
X    /* in the case where we are opening a user defined data type */
X    /* tree, that already exists, the pointer will not be set, */
X    /* because of the logic above (IE - it wont know its a userdef */
X    /* until it opens) so we set it using a macro from btree.h */
X    if(globargc == 2 && bt_dtype(globf) == BT_USRDEF)
X        bt_cmpfn(globf) = mycompare;
X}
X
X
Xvoid
Xdo_close()
X{
X    if(globf != NULL) {
X        if(bt_close(globf) == BT_OK)
X            (void)printf("closed OK\n");
X        else
X            (void)printf("error closing\n");
X    } else {
X        (void)printf("nothing open\n");
X    }
X    globf = NULL;
X}
X
X
X#ifdef    YES_BT_DEBUG
Xvoid
Xdo_pagedump()
X{
X    struct    bt_cache *p;
X    int    x;
X    off_t    num;
X
X    for(x = 1; x < globargc; x++) {
X        num = (off_t)atol(globargv[x]);
X        if(num == 0L) {
X            (void)printf("cannot read \"%s\" as a page #\n",globargv[x]);
X        } else {
X            if((p = bt_rpage(globf,num)) == NULL) {
X                (void)printf("cannot read page %ld\n",num);
X                return;
X            } else {
X                bt_dump(globf,p);
X            }
X        }
X    }
X}
X#endif
X
X
Xvoid
Xdo_quit()
X{
X    if(globf != NULL) {
X        (void)printf("closing %s\n",globname);
X        if(bt_close(globf) != BT_OK) {
X            (void)printf("problems closing %s\n",globname);
X            exit(1);
X        }
X    }
X    exit(0);
X}
X
X
Xvoid
Xdo_insert()
X{
X    caddr_t    ptr;
X    off_t    rrn;
X    static    off_t    rrnval = 1L;
X    int    len;
X
X    if((globargc > 2 && bt_dtype(globf) != BT_USRDEF))
X        rrn = atol(globargv[2]);
X    else
X        rrn = rrnval++;
X
X    ptr = encode(globargv[1],globargv[2],&len);
X
X    if(bt_insert(globf,ptr,len,rrn,0)== BT_ERR) {
X        bt_perror(globf,"error in insert");
X        return;
X    }
X}
X
X
Xvoid
Xdo_revload()
X{
X    caddr_t    ptr;
X    off_t    rrnval = 1L;
X    int    len;
X    FILE    *inp;
X    char    *p;
X    char    fuf[BUFSIZ];
X
X    if((inp = fopen(globargv[1],"r")) == NULL) {
X        perror(globargv[1]);
X        return;
X    }
X
X    /* call #1 to bt_load with flag BT_BOF to tell it to start */
X    if(bt_load(globf,0,0,0L,BT_BOF)== BT_ERR) {
X        bt_perror(globf,"cannot initialize btree load");
X        (void)fclose(inp);
X        return;
X    }
X
X    while(fgets(fuf,sizeof(fuf),inp) != NULL) {
X        if((p = rindex(fuf,'\n')) != NULL)
X            *p = '\0';
X
X        /* files of user def stuff must be tab separated */
X        /* for the purposes of this example. */
X        if(bt_dtype(globf) == BT_USRDEF) {
X            if((p = rindex(fuf,'\t')) != NULL) {
X                *p++ = '\0';
X            } else {
X                (void)fprintf(stderr,"user-defined data must be tabbed when reading from a file\n");
X                continue;
X            }
X        }
X
X        ptr = encode(fuf,p,&len);
X        if(bt_load(globf,ptr,len,rrnval++,BT_OK)== BT_ERR) {
X            bt_perror(globf,"error in load");
X            break;
X        } else
X            (void)printf(".");
X
X    }
X
X    /* a final call to bt_load with BT_EOF tells it to stop */
X    if(bt_load(globf,0,0,0L,BT_EOF) == BT_ERR) {
X        bt_perror(globf,"cannot shut down load");
X        (void)fclose(inp);
X        return;
X    }
X
X    (void)fclose(inp);
X    (void)printf("\ndone\n");
X}
X
X
Xvoid
Xdo_load()
X{
X    caddr_t    ptr;
X    off_t    rrnval = 1L;
X    int    len;
X    FILE    *inp;
X    char    *p;
X    char    fuf[BUFSIZ];
X
X    if((inp = fopen(globargv[1],"r")) == NULL) {
X        perror(globargv[1]);
X        return;
X    }
X
X    while(fgets(fuf,sizeof(fuf),inp) != NULL) {
X        if((p = rindex(fuf,'\n')) != NULL)
X            *p = '\0';
X
X        /* files of user def stuff must be tab separated */
X        /* for the purposes of this example. */
X        if(bt_dtype(globf) == BT_USRDEF) {
X            if((p = rindex(fuf,'\t')) != NULL) {
X                *p++ = '\0';
X            } else {
X                (void)fprintf(stderr,"user-defined data must be tabbed when reading from a file\n");
X                continue;
X            }
X        }
X
X        ptr = encode(fuf,p,&len);
X        if(bt_insert(globf,ptr,len,rrnval++,1)== BT_ERR) {
X            bt_perror(globf,"\nerror in insert");
X            break;
X        } else
X            (void)printf(".");
X    }
X    (void)fclose(inp);
X    (void)printf("\ndone\n");
X}
X
X
Xvoid
Xdo_help()
X{
X    struct    cmd    *c = cmds;
X    (void)printf("short list of commands::\n------------------------\n");
X    while(c->name != 0) {
X        (void)printf("%s\n",c->usage);
X        c++;
X    }
X}
X
X
Xvoid
Xdo_zap()
X{
X    if(bt_zap(globf) == BT_ERR) {
X        bt_perror(globf,"zap");
X        return;
X    }
X    (void)printf("zapped %s\n",globname);
X}
X
X
Xvoid
Xdo_stats()
X{
X    (void)printf("superblock:\n");
X    (void)printf("struct\tbt_super {\n\tlong\tmagic=%ld;\n",globf->sblk.magic);
X    (void)printf("\tint\tpsiz=%d;\n",bt_pagesiz(globf));
X    (void)printf("\tint\tdtype=%d;\n",bt_dtype(globf));
X    (void)printf("\tint\tlevs=%d;\n",globf->sblk.levs);
X    (void)printf("\toff_t\troot=%ld;\n",globf->sblk.root);
X    (void)printf("\toff_t\tfree=%ld;\n",globf->sblk.free);
X    (void)printf("\toff_t\thigh=%ld;\n};\n",globf->sblk.high);
X
X    (void)printf("struct\tbt_index {\n\tint\tfd=%d;\n",bt_fileno(globf));
X    (void)printf("\tchar\tdirt=%d;\n",globf->dirt);
X    (void)printf("\tint\tcflg=%d;\n",globf->cflg);
X    (void)printf("\tint\tcky=%d;\n",globf->cky);
X    (void)printf("\toff_t\tcpag=%ld;\n",globf->cpag);
X    (void)printf("\tint\tshih=%d;\n};\n",globf->shih);
X}
X
X
Xvoid
Xdo_find()
X{
X    off_t    rrnval;
X    caddr_t    ptr;
X    int    len;
X
X    ptr = encode(globargv[1],globargv[2],&len);
X
X    switch(bt_find(globf,ptr,len,&rrnval)) {
X        case BT_OK:
X            (void)printf("found with pointer val=%ld\n",rrnval);
X            break;
X
X        case BT_NF:
X            (void)printf("key not found.\n");
X            break;
X
X        case BT_ERR:
X            bt_perror(globf,"find failed");
X            break;
X
X        default:
X            (void)printf("this should never happen!\n");
X    }
X}
X
X
Xvoid
Xdo_goto(whence)
Xint    whence;
X{
X    if(bt_goto(globf,whence) == BT_ERR)
X        bt_perror(globf,"error - cannot seek to EOF/BOF of tree!");
X
X
X}
X
X
Xvoid
Xdo_tail()
X{
X    do_goto(BT_EOF);
X}
X
X
Xvoid
Xdo_head()
X{
X    do_goto(BT_BOF);
X}
X
X
Xvoid
Xdo_traverse(whence)
Xint    whence;
X{
X    char    buf[BUFSIZ];
X    int    retlen;
X    off_t    rrv;
X    int    x;
X    int    cnt;
X    int    ret;
X
X    /* users should not probably look at this */
X    if(globf->cpag == BT_NULL)
X        (void)printf("(no currently defined location in tree)\n");
X
X    if(globargc == 1)
X        cnt = 1;
X    else
X        cnt = atoi(globargv[1]);
X
X    for(x = 0; x < cnt; x++) {
X        ret = bt_traverse(globf,whence,buf,BUFSIZ,&retlen,&rrv);
X        switch(ret) {
X            case BT_ERR:
X                bt_perror(globf,"cannot traverse to key!");
X                return;
X
X            case BT_EOF:
X                (void)printf("EOF.\n");
X                break;
X
X            case BT_BOF:
X                (void)printf("BOF.\n");
X                break;
X
X            case BT_OK:
X                printk(buf,retlen,rrv);
X                break;
X
X            default:
X                (void)printf("this should never happen!\n");
X        }
X
X        if(ret == whence)
X            return;
X    }
X}
X
X
Xvoid
Xdo_next()
X{
X    do_traverse(BT_EOF);
X}
X
X
Xvoid
Xdo_prev()
X{
X    do_traverse(BT_BOF);
X}
X
X
Xvoid
Xdo_dump()
X{
X    char    buf[BUFSIZ];
X    int    ret;
X    int    retlen;
X    off_t    junk;
X    int    d;
X
X    if(globargc > 1) {
X        d = BT_BOF;
X        if(bt_goto(globf,BT_EOF) == BT_ERR) {
X            bt_perror(globf,"cannot goto EOF");
X            return;
X        }
X    } else {
X        d = BT_EOF;
X        if(bt_goto(globf,BT_BOF) == BT_ERR) {
X            bt_perror(globf,"cannot goto BOF");
X            return;
X        }
X    }
X
X    while((ret = bt_traverse(globf,d,buf,BUFSIZ,&retlen,&junk)) == BT_OK) {
X        printk(buf,retlen,junk);
X    }
X    if(ret == BT_ERR)
X        bt_perror(globf,"error traversing!");
X}
X
X
X#ifdef    YES_BT_DEBUG
Xvoid
Xdo_struct()
X{
X    off_t    rrv;
X    struct    bt_cache *p;
X
X    (void)printf("levels:%d\t\troot:%ld\n",globf->sblk.levs,globf->sblk.root);
X
X
X    rrv = bt_pagesiz(globf);
X    (void)printf("Index Pages:\n");
X    while(rrv < globf->sblk.high && ((p = bt_rpage(globf,rrv)) != NULL)) {
X        if(HIPT(p->p) != BT_NULL && HIPT(p->p) != BT_FREE)
X            bt_dump(globf,p);
X        rrv += bt_pagesiz(globf);
X    }
X
X    rrv = bt_pagesiz(globf);
X    (void)printf("\nLeaf Pages:\n");
X    while(rrv < globf->sblk.high && ((p = bt_rpage(globf,rrv)) != NULL)) {
X        if(HIPT(p->p) == BT_NULL)
X            bt_dump(globf,p);
X        rrv += bt_pagesiz(globf);
X    }
X}
X#endif
X
X
Xvoid
Xdo_wlabel()
X{
X    /* write label size + 1 to include null terminator - hack */
X    if(bt_wlabel(globf,globargv[1],strlen(globargv[1]) + 1) == BT_ERR) {
X        bt_perror(globf,"cannot write label");
X        return;
X    }
X}
X
X
Xvoid
Xdo_rlabel()
X{
X    char    lbuf[BUFSIZ];
X
X    /* sample read-back of label */
X    if(bt_rlabel(globf,lbuf,BUFSIZ) == BT_ERR) {
X        bt_perror(globf,"cannot read label");
X        return;
X    }
X
X    (void)printf("tree label is \"%s\"\n",lbuf);
X}
X
X
Xvoid
Xdo_delete()
X{
X    int    len;
X    caddr_t    ptr;
X
X    ptr = encode(globargv[1],globargv[2],&len);
X    switch(bt_delete(globf,ptr,len)) {
X        case BT_OK:
X            (void)printf("deleted.\n");
X            break;
X
X        case BT_NF:
X            (void)printf("key not found.\n");
X            break;
X
X        case BT_ERR:
X            bt_perror(globf,"delete failed");
X            break;
X
X        default:
X            (void)printf("this should never happen!\n");
X    }
X}
X
X
Xcaddr_t
Xencode(b1,b2,lp)
Xchar    *b1;
Xchar    *b2;
Xint    *lp;
X{
X    static    int    iv;
X    static    float    fv;
X    static    long    lv;
X    static    struct    point    p;
X
X    /* since this test program uses a bunch of data types, this */
X    /* function interprets the arguments based on what the user */
X    /* enters, places them in a buffer of the appropriate type */
X    /* and returns a pointer to it. this is somewhat gross, but */
X    /* for the purposes of example should suffice. presumably */
X    /* "real" applications wont need to do all this kinda stuff */
X    /* the encoded length is stashed in the provided pointer */
X
X    switch(bt_dtype(globf)) {
X        case    BT_STRING:
X            /* interpret input as a string. just return it */
X            *lp = strlen(b1);
X            return(b1);
X
X        case    BT_INT:
X            iv = atoi(b1);
X            *lp = (int)sizeof(int);
X            return((caddr_t)&iv);
X            break;
X
X        case    BT_LONG:
X            lv = atol(b1);
X            *lp = (int)sizeof(long);
X            return((caddr_t)&lv);
X            break;
X
X        case    BT_FLOAT:
X            fv = atof(b1);
X            *lp = (int)sizeof(float);
X            return((caddr_t)&fv);
X            break;
X
X        case    BT_USRDEF:
X            /* this is somewhat gross, but you get the idea */
X            if(b1 != NULL)
X                p.xcoord = atoi(b1);
X            else
X                p.xcoord = 0;
X            if(b2 != NULL)
X                p.ycoord = atoi(b2);
X            else
X                p.ycoord = 0;
X            *lp = (int)sizeof(p);
X            return((caddr_t)&p);
X    }
X    return(NULL);
X}
X
X
Xvoid
Xprintk(buf,rl,rv)
Xcaddr_t    buf;
Xint    rl;
Xoff_t    rv;
X{
X    struct    point *p;
X    char    *cp;
X
X    switch(bt_dtype(globf)) {
X        case    BT_STRING:
X            buf[rl] = '\0';
X            cp = buf;
X            (void)printf("key=\"");
X            while(*cp != '\0') {
X                if(isprint(*cp))
X                    (void)printf("%c",*cp);
X                else
X                    (void)printf("(0x%x)",*cp);
X                cp++;
X            }
X            (void)printf("\",len=%d,rrv=%ld",rl,rv);
X            break;
X
X        case    BT_INT:
X            (void)printf("key=%d,rrv=%ld",*(int *)buf,rv);
X            break;
X
X        case    BT_LONG:
X            (void)printf("key=%ld,rrv=%ld",*(long *)buf,rv);
X            break;
X
X        case    BT_FLOAT:
X            (void)printf("key=%f,rrv=%ld",*(float *)buf,rv);
X            break;
X
X        case    BT_USRDEF:
X            /* here we are pretending it is a struct point* */
X            p = (struct point *)&buf[0];
X            (void)printf("point=(%d,%d),rrv=%ld",p->xcoord,p->ycoord,rv);
X            break;
X    }
X    (void)printf("\n");
X}
X
X
X/* sample comparison function for user defined data type. NOTE - I have */
X/* kinda played loose here, since s1 and s2 are really caddr_ts not pointers */
X/* to struct points, but this should work just fine. kinda sloppy, though. */
Xmycompare(s1,l1,s2,l2)
Xstruct point     *s1;
Xint    l1;
Xstruct point    *s2;
Xint    l2;
X{
X    /* since we are using a struct, the lengths are irrelevant */
X    if(s1->xcoord == s2->xcoord) {
X        if(s1->ycoord == s2->ycoord)
X            return(0);
X        else
X            return(s1->ycoord - s2->ycoord);
X    }
X    return(s1->xcoord - s2->xcoord);
X}
END_OF_FILE
if test 18333 -ne `wc -c <'b+tree/utils/btest.c'`; then
    echo shar: \"'b+tree/utils/btest.c'\" unpacked with wrong size!
fi
# end of 'b+tree/utils/btest.c'
fi
echo shar: End of archive 5 \(of 5\).
cp /dev/null ark5isdone
MISSING=""
for I in 1 2 3 4 5 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 5 archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0